/*
 * @lc app=leetcode.cn id=697 lang=cpp
 *
 * [697] 数组的度
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        int res = 0;
        if (nums.empty()){return res;}
        std::map<int, NumInfo> numsInfo;
        for (int index = 0;index < nums.size();index++){
            auto numIter = numsInfo.find(nums[index]);
            if (numIter==numsInfo.end()){
                numsInfo.emplace(nums[index], NumInfo(index));
// printf("new %d \n", nums[index]);
            } else{
                numIter->second.times_ += 1;
                numIter->second.endIndex_ = index;
// printf("old %d : %d %d %d\n", nums[index], 
// numIter->second.times_,
// numIter->second.startIndex_,
// numIter->second.endIndex_
// );
            }
        }
        int mostOccurrencesNum = 0;
        NumInfo mostOccurrencesNumInfo(0);
        mostOccurrencesNumInfo.times_ = 0;

        for (auto& infoIter : numsInfo){
            if (infoIter.second.times_ > mostOccurrencesNumInfo.times_){
                mostOccurrencesNum = infoIter.first;
                mostOccurrencesNumInfo.times_ = infoIter.second.times_;
                mostOccurrencesNumInfo.endIndex_ = infoIter.second.endIndex_;
                mostOccurrencesNumInfo.startIndex_ = infoIter.second.startIndex_;                
            }
            else if (infoIter.second.times_ == mostOccurrencesNumInfo.times_){
// printf(" %d %d %d : %d %d %d\n",
// infoIter.first,
// infoIter.second.endIndex_,
// infoIter.second.startIndex_,
// mostOccurrencesNum,
// mostOccurrencesNumInfo.endIndex_,
// mostOccurrencesNumInfo.startIndex_
// );
                if (infoIter.second.endIndex_-infoIter.second.startIndex_
                < mostOccurrencesNumInfo.endIndex_-mostOccurrencesNumInfo.startIndex_){
                    mostOccurrencesNum = infoIter.first;
                    mostOccurrencesNumInfo.endIndex_ = infoIter.second.endIndex_;
                    mostOccurrencesNumInfo.startIndex_ = infoIter.second.startIndex_;                    
// printf("change to %d \n", mostOccurrencesNum);
                }
            }
        }
        auto resIter = numsInfo.find(mostOccurrencesNum);
        res = resIter->second.endIndex_ - resIter->second.startIndex_ + 1;
        return res;
    }
private:
    struct NumInfo{
        int times_;
        int startIndex_;
        int endIndex_;
        NumInfo(int startIndex) :
        times_(1),
        startIndex_(startIndex),
        endIndex_(startIndex)
        {}
    };
};
// @lc code=end

